package org.example.top40;

public class main30 {
    //接雨水
    //输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    //输出：6
    //思路：左,右dp数组 填充
    //填充完后在遍历一遍min-height[i]
    public static void main(String[] args) {
        int[] height={0,1,0,2,1,0,1,3,2,1,2,1};
        int len=height.length;
        int[] leftMax=new int[len];
        int[] rightMax=new int[len];
        leftMax[0]=height[0];
        for (int i = 1; i < len; i++) {
            leftMax[i]=Math.max(leftMax[i-1],height[i]);
        }
        //注意不要思维惯性！！！
        rightMax[len]=height[len-1];
        for (int i = len-2; i >=0; i--) {
            rightMax[i]=Math.max(rightMax[i+1],height[i] );
        }
        int res=0;
        for (int i = 1; i < len-1; i++) {
            res+=Math.min(leftMax[i],rightMax[i])-height[i];
        }
        System.out.println(res);
    }
}
